The present invention relates generally to digital data processing devices and, more specifically, to bus arbitration in such devices.
As the performance demands on digital data processing devices continue to increase at a meteoric pace, processors have been developed which operate at higher and higher clock speeds. The instruction sets used to control processors have been pared down (e.g., RISC architecture) to make them more efficient. Processor improvements alone, however, have been insufficient to provide the greater performance required by users. The other subsystems which support the processor, e.g., I/O devices and memory devices, must also be designed to operate at higher speeds and support greater bandwidth. In the color printing industry, for example, the demand for greater print resolution and color quality requires tremendous data throughput to satisfy. To accommodate these requirements, functions can be delegated to special processors (e.g., co-processors, ASICs, etc.) which operate in tandem with a central processor to speed up processing. These multi-processor systems typically share system resources for economy and efficiency.
Buses convey data and instructions between elements of digital processing systems including the shared resources mentioned above. Commonly three types or portions of buses are provided, i.e., control, address and data, each of which convey the different types of information connoted by their names. Alternatively, address and data can be multiplexed together on one bus. Local buses provide data transmission capability within a device, whereas system buses connect system components, such as an I/O subsystem, a memory subsystem and a processor, together. In industry parlance, devices which can control the system bus are termed bus masters, while other devices, which are passive and respond to requests from the bus masters, are termed slaves. Some devices may operate either as a slave or a bus master at different times to accomplish different objectives. In many systems, several bus masters compete concurrently for use of the system bus.
In order to avoid bus contention, i.e., the situation where two bus masters have simultaneous control over the system bus, a bus arbiter can be provided to arbitrate between simultaneous requests to use the bus. In such systems, a device which wishes to control the bus will send a bus request signal to the arbiter over a control line. If the arbiter grants the bus request, then an acknowledgement or granting signal is transmitted back to the requesting device over another control line. The methodology by which the arbiter prioritizes requests is called the bus arbitration priority scheme. These priority schemes can be implemented as an ordered list of bus masters (i.e., the highest requesting bus master on the list receives the next bus grant) or as state machines inside the arbiter which provide "round robin" bus access to the bus masters. Both types of bus arbitration priority schemes are described in more detail below. Typically, the priority assigned to each bus master in an arbiter is fixed at the time of system implementation and does not change when the system is in operation.
Each bus master has at least two requirements. One requirement is bus latency, that is, how long a bus master waits to be granted the bus after a bus request is issued. The other requirement is bandwidth, which refers to the amount of data to be moved along a system bus in a unit of time, e.g., a certain number of Mbytes/s. In order for bus operations to be performed smoothly, each bus request should be serviced with a sufficiently short bus latency and with a sufficient bandwidth.
As the number of processors in a system increases (and accordingly the number of potential bus masters), the selection of an appropriate arbitration scheme becomes more important in order to optimize bus latency and bandwidth. Consider a digital processing system in which seven bus masters vie for ownership of the system bus. In ordered arbitration priority schemes, a fixed priority is assigned to the bus masters according to the importance of each bus master's function to the system. When simultaneous bus requests are received, the bus is granted to the requesting bus master that has the highest priority and that bus master is not obligated to release the bus unless a higher priority bus master subsequently requests the bus. Under this scenario it is likely that the lowest priority bus master will experience situations where neither its latency nor its bandwidth requirements are fulfilled because this bus master must wait a potentially infinite amount of time to get the bus, and then it may be allowed to use the bus for only a short period of time if any of the other bus masters want the bus.
In another conventional bus arbitration priority scheme, commonly referred to as a "round robin" priority scheme, a bus master which has just completed a bus operation is not granted the bus for a second operation until all other requesting bus masters have first been granted the bus. Thus a round robin arbitration priority scheme is not likely to fulfill each bus master's latency requirement, particularly in systems having many bus masters.